// 解题思路：
// 解法 1：动态规划，找出所有回文串，求出最大长度
// 解法 2：中心扩展算法，以 i 位置为中心，向左右扩展，利用回文串的特性（左右两个字符相同）

public class PalindromStringLength {
    // 解法 1：动态规划算法
    public int getLongestPalindrome (String A) {
        // write code here
        int n = A.length();
        char[] arr = A.toCharArray();

        boolean[][] dp = new boolean[n][n];

        int ret = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= i; j++){
                if(arr[j] == arr[i]){
                    if(j == i || j + 1 == i){
                        dp[j][i] = true;
                    }else{
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                }else{
                    dp[j][i] = false;
                }
                if(dp[j][i] == true){
                    ret = Math.max(ret, i - j + 1);
                }
            }
        }
        return ret;
    }

    // 解法 2： 中心扩展算法
    public int getLongestPalindrome2 (String A) {
        // write code here
        int n = A.length();
        char[] arr = A.toCharArray();
        int left = 0;
        int right = 0;

        int ret = 0;
        for(int i = 0; i < n; i++){
            left = i - 1;
            right = i + 1;
            while(left >= 0 && right < n && arr[left] == arr[right]){
                left--;
                right++;
            }
            ret = Math.max(ret, right - left - 1);
        }

        for(int i = 0; i < n; i++){
            left = i;
            right = i + 1;
            while(left >= 0 && right < n && arr[left] == arr[right]){
                left--;
                right++;
            }
            ret = Math.max(ret, right - left - 1);
        }

        return ret;
    }
}
